package com.example.myletcodelearing.kmp





/**
 * @author tgw
 * @date 2022/8/6
 * @describe
 */


fun main(array: Array<String>) {
    println("kmp：开始")
    var S = "123123123125123"
    var T = "123125"
    var test=KmpTest()
    var index2 =test.bf(S,T)
    var index3 =test.KMP(S,T)
    println("kmp：暴力法找到$index2")
    println("kmp：kmp法找到$index3")
    println("kmp：kmp找到字串的标记：${test.getNext(T).asList().toString()}")

}

class KmpTest {

    val S = intArrayOf(1,2,3,1,2,3,1,2,3,1,2,5,1,2,3)
    val T = intArrayOf(1,2,3,1,2,5)


//    fun indexSub(S:IntArray,T:IntArray,index:Int?=null):Int?{
//        var i=0 //主串位置下标
//        var j=0 //子串位置下标
//        var next:Array<Int?>  = arrayOfNulls(255)
//        next[0] = 0
//        getNext(T,next)
//        while (i<S.size && j<T.size){
//            if (j==0 || S[i]==T[j]){
//                i++
//                j++
//            }else{
//                 next[j]?.let {
//                     j = it
//                }
//            }
//        }
//        if (j>T.size){
//           return i-T.size
//        }else{
//            return 0
//        }
//    }
//
//    //串的 前缀与后缀的相同元素的个数，然后记录到next数组，如ababc对应01123
//    fun getNext(S:IntArray,next:Array<Int?>){
//        var i=1 //后缀
//        var j=0 //前缀
//        next[1] = 0
//        while (i<S.size){
//            if (j==0||S[i] ==S[j]){
//                ++i
//                ++j
//                next[i] = j
//            }else{
//                next[j]?.let {
//                    j=it
//                }
//            }
//        }
//    }

    /**
     *
     * 暴力破解法
     * @param ts 主串
     * @param ps 模式串
     * @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1
     */
    fun bf(ts: String, ps: String): Int {
        val t = ts.toCharArray()
        val p = ps.toCharArray()
        var i = 0 // 主串的位置
        var j = 0 // 模式串的位置
        while (i < t.size && j < p.size) {
            if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
                i++
                j++
            } else {
                i = i - j + 1 // 一旦不匹配，i后退
                j = 0 // j归0
            }
        }
        return if (j == p.size) {
            i - j
        } else {
            -1
        }
    }

    fun kmp1(ts: String, ps: String): Int {
        val t = ts.toCharArray()
        val p = ps.toCharArray()
        val next = IntArray(p.size)
        var i = 0 // 主串的位置
        var j = 0 // 模式串的位置
        while (i < t.size && j < p.size) {
            if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
                i++
                j++
                next[i] = j
            } else {
//              j =
            }
        }
        return if (j == p.size) {
            i - j
        } else {
            -1
        }
    }
    //字串的 前缀与后缀的相同元素的个数，然后记录到next数组，如ababc对应-10012

    //如果母串为ababababc，查找到第五个的时候，第五个母串的a与字串的c,不相等，
    // 这时候将母串的第五个字母a,应该与字串的next【4】=2，想当于和子串下标为2的值比较
    fun getNext(ps: String): IntArray {
        val p = ps.toCharArray()
        val next = IntArray(p.size)
        next[0] = -1
        var j = 0
        var k = -1
        while (j < p.size - 1) {
            if (k == -1 || p[j] == p[k]) {
                ++j
                ++k
                next[j] = k
            } else {
                k = next[k]
            }
        }
        return next
    }

    fun KMP(ts: String, ps: String): Int {
        val t = ts.toCharArray()
        val p = ps.toCharArray()
        var i = 0 // 主串的位置
        var j = 0 // 模式串的位置
        val next = getNext(ps)
        while (i < t.size && j < p.size) {
            if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
                i++
                j++
            } else {
                // i不需要回溯了
                // i = i - j + 1;
                j = next[j] // j回到指定位置
            }
        }
        return if (j == p.size) {
            i - j
        } else {
            -1
        }
    }

}

